package com.zxy.javaarithmetic.chapter_2_LinkList;

import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_12_ReverseKNode
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/28 15:03
 *  @描述：    逆序k个节点,最后节点不够k个的不做调整，例如 1-2-3-4-5-6-7-8，k=3,调整之后变成 3-2-1-6-5-4-7-8
 */
public class P_12_ReverseKNode {

    public static void main(String[] args) {
        Node head = LinkListUtils.getNode(8);
        LinkListUtils.printNode(head);
        LinkListUtils.printNode(reverseKNode1(head, 3));
    }

    private static void reverse(Node left, Node start, Node end, Node right) {
        Node pre = right;
        Node cur = start;
        Node next;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        if (left != null) {
            left.next = end;
        }
    }

    private static Node reverseKNode1(Node head, int k) {
        if (head == null || k < 2) {
            return head;
        }

        Node cur = head;
        Node start = null;
        Node left = null;
        Node next = null;
        int count = 1;

        while (cur != null) {
            next = cur.next;
            if (count == k) {
                start = left == null ? head : left.next;
                head = left == null ? cur : head;
                reverse(left, start, cur, next);
                left = start;
                count = 0;
            }
            count++;
            cur = next;
        }

        return head;
    }

    private static Node reverseKNode2(Node head, int k) {
        if (head == null || k < 2) {
            return head;
        }
        Stack<Node> stack = new Stack<>();
        Node newHead = null;
        Node lastTail = null;
        while (head != null) {
            stack.push(head);
            head = head.next;

            if (stack.size() == k) {
                if (newHead == null) {
                    newHead = stack.pop();
                    lastTail = newHead;
                }
                while (!stack.isEmpty()) {
                    lastTail.next = stack.pop();
                    lastTail = lastTail.next;
                }
                lastTail.next = head;
            }
        }

        return newHead;
    }
}
